/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.acworks.acroute.v2.impl;

import com.acworks.acroute.v2.Arc;
import com.acworks.acroute.v2.ArcDirectionType;
import com.acworks.acroute.v2.ImmutableGraph;
import com.acworks.acroute.v2.Node;
import com.acworks.acroute.v2.NodeType;
import com.acworks.acroute.v2.Path;
import com.acworks.acroute.v2.PathAwareGraph;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 *
 * @author nikita
 */
public class PathImpl implements Path {

    final private ImmutableGraph graph;
    final private LinkedList<Node> pathNodes;
    final private Map<Node, SortedSet<Node>> unvisitedSuccessorMap;

    public PathImpl(ImmutableGraph graph) {
        assert graph != null;
        this.graph = graph;
        this.unvisitedSuccessorMap = new HashMap<Node, SortedSet<Node>>();
        pathNodes = new LinkedList<Node>();
        advanceCurrentNode(graph.getStartingNode());
    }

    /**
     * make given node current, update unvisitedSuccessorMap.
     * if current node already exists, 'node' must be a successor
     *
     * @param node
     * @throw IllegalArgumentException if 'currentNode' already exists and 'node'
     * is not a successor
     */
    private void advanceCurrentNode(Node node) {
        assert node != null;

        if (pathNodes.contains(node)) {
            throw new IllegalArgumentException("cannot advance to node " + node + " as it's already in this path");
        }

        Node prevCurrentNode = pathNodes.isEmpty() ? null : pathNodes.getLast();

        if (prevCurrentNode != null) {
            Set<Node> unvisitedSuccessorsOfPrevCurrentNode = unvisitedSuccessorMap.get(prevCurrentNode);
            if (!unvisitedSuccessorsOfPrevCurrentNode.contains(node)) {
                throw new IllegalArgumentException(node + " isn't among unvisited successors of current node: " + prevCurrentNode);
            }
            unvisitedSuccessorsOfPrevCurrentNode.remove(node);
        }

        SortedSet<Node> unvisitedSuccessors = new TreeSet<Node>(node.getSuccessors());
        pathNodes.addLast(node);
        unvisitedSuccessorMap.put(node, unvisitedSuccessors);
    }

    @Override
    public boolean isAtStartNode() {
        return getCurrentNode().getType() == NodeType.STARTING;
    }

    /**
     *
     * @return true only if:
     * there are no unvisited nodes and
     */
    @Override
    public boolean isHamiltonianPath() {
        return graph.getNodes().equals(new HashSet<Node>(getPathNodes()));
    }

    @Override
    public void popCurrentNode() {
        if (isAtStartNode()) {
            throw new RuntimeException("already at the starting node");
        }

        Node deletedNode = pathNodes.removeLast();
        unvisitedSuccessorMap.remove(deletedNode);
    }

    @Override
    public void advanceToNextUnvisitedSuccessor() {

        advanceCurrentNode(getNextUnvisitedSuccessor());
    }

    Node getCurrentNode() {
        return pathNodes.getLast();
    }

    private Node getNextUnvisitedSuccessor() {
        SortedSet<Node> unvisitedSuccessors = unvisitedSuccessorMap.get(getCurrentNode());
        if (unvisitedSuccessors != null) {
            for (Node successor : unvisitedSuccessors) {
                if (!pathNodes.contains(successor)) {
                    return successor;
                }
            }
        }
        return null;
    }

    @Override
    public boolean currentNodeHasUnvisitedSuccessors() {

        return getNextUnvisitedSuccessor() != null;
    //return unvisitedSuccessors != null && (!unvisitedSuccessors.isEmpty());
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final PathImpl other = (PathImpl) obj;
        if (this.pathNodes != other.pathNodes && (this.pathNodes == null || !this.pathNodes.equals(other.pathNodes))) {
            return false;
        }
        return true;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 83 * hash + (this.pathNodes != null ? this.pathNodes.hashCode() : 0);
        return hash;
    }

    @Override
    public List<Node> getPathNodes() {
        return pathNodes;
    }

    @Override
    public String toString() {
        return super.toString() + "[pathNodes=" + pathNodes + "]";
    }

    @Override
    public boolean advanceToNextUnvisitedSuccessor(PathAwareGraph pag) {
        assert pag != null;

        Node currentNode = getCurrentNode();
        assert currentNode != null;

        SortedSet<Node> unvisitedSuccessors = unvisitedSuccessorMap.get(currentNode);
        assert unvisitedSuccessors != null;

        Node nextNode = null;
        for (Node successor : unvisitedSuccessors) {
            Arc connectingArc = GraphUtil.findConnectingArc(currentNode, successor, pag.getArcs());
            if (connectingArc != null &&
                    (connectingArc.getSourceNode().equals(currentNode) || connectingArc.getType() == ArcDirectionType.UNDIRECTED) && !pathNodes.contains(successor)) {
                nextNode = successor;
                break;
            }
        }

        if (nextNode != null) {
            advanceCurrentNode(nextNode);
            return true;
        } else {
            return false;
        }
    }
}
